package cn.initcap.algorithm.leetcode;

/**
 * @author initcap
 * @date Created in 2021/3/2 09:22.
 */
public class NumMatrix {

    int sum[][];

    public NumMatrix(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        sum = new int[m + 1][n + 1];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int top = 0, left = 0, leftTop = 0;
                if (i != 0) {
                    top = sum[i][j + 1] - sum[i][j];
                }
                if (j != 0) {
                    left = sum[i + 1][j] - sum[i][j];
                }
                if (i != 0 && j != 0) {
                    leftTop = sum[i][j];
                }
                sum[i + 1][j + 1] = matrix[i][j] + top + left + leftTop;
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        int top = 0, left = 0, leftTop = 0;
        if (row1 != 0) {
            top = sum[row1][col2 + 1] - sum[row1][col1];
        }
        if (col1 != 0) {
            left = sum[row2 + 1][col1] - sum[row1][col1];
        }
        if (row1 != 0 && col1 != 0) {
            leftTop = sum[row1][col1];
        }
        return sum[row2 + 1][col2 + 1] - top - left - leftTop;
    }

    public static void main(String[] args) {
        NumMatrix matrix = new NumMatrix(new int[][]{{3,0,1,4,2},{5,6,3,2,1},{1,2,0,1,5},{4,1,0,1,7},{1,0,3,0,5}});
        int res = matrix.sumRegion(2,1,4,3);
        System.out.println(res);
    }
}
